数え上げとは、実際に物を一つずつ数えるという面倒な作業なしに有限集合の大きさを決定する技術です。論理的な構造を活用することで、シンプルなメニューの組み合わせから複雑な暗号化の順列まで、さまざまな問題を解くことができます。
"または"と"かつ"の論理
組合せ論の全体を支える二つの柱があります。その適用は、タスクを複数のカテゴリの中から一つを選ぶことと見なすか、あるいは一連の選択の連続と見なすかによって完全に異なります。
加法原理（和則）
集合 $X$ が互いに重ならない部分集合 $X_1, X_2, \dots, X_n$ に分割されている場合、$X$ の要素の総数 $|X|$ はこれらの部分集合のサイズの和になります：
$$|X| = |X_1| + |X_2| + \dots + |X_n|$$
例え話： メインコースのメニューからサンドイッチを選んだり、前菜のメニューから前菜を選んだりして、カイズ・クイックランチで食事を選ぶ場合。両方を同時に注文することはできません。一つだけ選びます。
乗法原理（積則）
ある活動が $t$ 個の順次的な段階から成り立っており、段階 $i$ には $n_i$ 種類の結果がある場合、タスクを完了する方法の総数は各段階での可能性の積になります：
$$N = n_1 \times n_2 \times \dots \times n_t$$
例え話： "ビッグピックアップ"トラックの設定。エンジン（5種類）とキャブスタイル（3種類）の両方を選ばなければなりません。全構成は $5 \times 3 = 15$ 通りです。
コード実装と計算量
コンピュータサイエンスでは、これらの原則はループ構造として現れます。直列のループは加法原理を表し、ネストされたループは乗法原理を表します。
// 加法原理（m + n 回の実行）
for i = 1 to m: println(i)
for j = 1 to n: println(j)
// 乗法原理（m × n 回の実行）
for i = 1 to m:
for j = 1 to n:
println(i, j)
for i = 1 to m: println(i)
for j = 1 to n: println(j)
// 乗法原理（m × n 回の実行）
for i = 1 to m:
for j = 1 to n:
println(i, j)
🎯 核心原則
キーワードで区別しましょう："または"は加法（排他的な選択）を意味し、"かつ"や"順次"は乗法（独立した段階の連続）を意味します。